package com.example.demo.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 链接：<a href="https://leetcode.cn/problems/jump-game-vi/description/?envType=daily-question&envId=2024-02-05">https://leetcode.cn/problems/jump-game-vi/description/?envType=daily-question&envId=2024-02-05</a>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/05 10:00
 */
public class _1696_跳跃游戏Ⅵ {


    public static void main(String[] args) {
        int[] nums = new int[]{1, -1, -2, 4, -7, 3};

        int[] nums1 = new int[]{10, -5, -2, 4, 0, 3};

        int[] nums2 = new int[]{1, -5, -20, 4, -1, 3, -6, -3};

        int[] nums3 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

        int i = maxResult(nums, 2);
        System.out.println(i);
    }

    public static int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(0);
        for (int i = 1; i < n; i++) {
            while (queue.peekFirst() < i - k) {
                queue.pollFirst();
            }
            dp[i] = dp[queue.peekFirst()] + nums[i];
            while (!queue.isEmpty() && dp[queue.peekLast()] <= dp[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return dp[n - 1];
    }
}